#include <vector>
#include <queue>
#include <iostream>

using namespace std;

class Solution 
{
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) 
    {
        vector<int> result;
        deque<int> q;
        if(k > nums.size() || nums.size() == 0)
        {
            return result;
        }
        q.push_back(nums[0]);
        for(int i = 1; i < k; i++)
        {
            while(!q.empty() && nums[i] > q.back())
            {
                q.pop_back();
            }
            q.push_back(nums[i]);
        }
        result.push_back(q.front());
        for(int i = k; i < nums.size(); i++)
        {
            if(q.front() == nums[i - k])
            {
                q.pop_front();
            }
            while(!q.empty() && nums[i] > q.back())
            {
                q.pop_back();
            }
            q.push_back(nums[i]);
            result.push_back(q.front());
        }
        return result;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) 
{
    cout << "[";
    for(int i = 0; i < nums.size(); i++) 
    {
        cout << nums[i];
        if(i < nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() 
{
    Solution solution;
    
    // 测试案例1: [1,3,-1,-3,5,3,6,7], k = 3
    cout << "测试案例1:" << endl;
    vector<int> nums1 = {1, 3, -1, -3, 5, 3, 6, 7};
    int k1 = 3;
    cout << "输入: nums = ";
    printArray(nums1);
    cout << ", k = " << k1 << endl;
    vector<int> result1 = solution.maxSlidingWindow(nums1, k1);
    cout << "输出: ";
    printArray(result1);
    cout << endl;
    cout << "期望: [3,3,5,5,6,7]" << endl << endl;
    
    // 测试案例2: [1], k = 1
    cout << "测试案例2:" << endl;
    vector<int> nums2 = {1};
    int k2 = 1;
    cout << "输入: nums = ";
    printArray(nums2);
    cout << ", k = " << k2 << endl;
    vector<int> result2 = solution.maxSlidingWindow(nums2, k2);
    cout << "输出: ";
    printArray(result2);
    cout << endl;
    cout << "期望: [1]" << endl << endl;
    
    // 测试案例3: k等于数组长度
    cout << "测试案例3 (k等于数组长度):" << endl;
    vector<int> nums3 = {1, 2, 3, 4, 5};
    int k3 = 5;
    cout << "输入: nums = ";
    printArray(nums3);
    cout << ", k = " << k3 << endl;
    vector<int> result3 = solution.maxSlidingWindow(nums3, k3);
    cout << "输出: ";
    printArray(result3);
    cout << endl;
    cout << "期望: [5]" << endl << endl;
    
    // 测试案例4: 递增序列
    cout << "测试案例4 (递增序列):" << endl;
    vector<int> nums4 = {1, 2, 3, 4, 5, 6};
    int k4 = 3;
    cout << "输入: nums = ";
    printArray(nums4);
    cout << ", k = " << k4 << endl;
    vector<int> result4 = solution.maxSlidingWindow(nums4, k4);
    cout << "输出: ";
    printArray(result4);
    cout << endl;
    cout << "期望: [3,4,5,6]" << endl << endl;
    
    // 测试案例5: 递减序列
    cout << "测试案例5 (递减序列):" << endl;
    vector<int> nums5 = {6, 5, 4, 3, 2, 1};
    int k5 = 3;
    cout << "输入: nums = ";
    printArray(nums5);
    cout << ", k = " << k5 << endl;
    vector<int> result5 = solution.maxSlidingWindow(nums5, k5);
    cout << "输出: ";
    printArray(result5);
    cout << endl;
    cout << "期望: [6,5,4,3]" << endl << endl;
    
    // 测试案例6: 包含负数
    cout << "测试案例6 (包含负数):" << endl;
    vector<int> nums6 = {1, 3, 1, 2, 0, 5};
    int k6 = 3;
    cout << "输入: nums = ";
    printArray(nums6);
    cout << ", k = " << k6 << endl;
    vector<int> result6 = solution.maxSlidingWindow(nums6, k6);
    cout << "输出: ";
    printArray(result6);
    cout << endl;
    // cout << "期望: [7,7,7,7,7]" << endl << endl;
    
    // 测试案例7: 相同元素
    cout << "测试案例7 (相同元素):" << endl;
    vector<int> nums7 = {3, 3, 3, 3, 3};
    int k7 = 2;
    cout << "输入: nums = ";
    printArray(nums7);
    cout << ", k = " << k7 << endl;
    vector<int> result7 = solution.maxSlidingWindow(nums7, k7);
    cout << "输出: ";
    printArray(result7);
    cout << endl;
    cout << "期望: [3,3,3,3]" << endl << endl;
    
    // 测试案例8: k=1
    cout << "测试案例8 (k=1):" << endl;
    vector<int> nums8 = {4, -2, 1, -3, 5};
    int k8 = 1;
    cout << "输入: nums = ";
    printArray(nums8);
    cout << ", k = " << k8 << endl;
    vector<int> result8 = solution.maxSlidingWindow(nums8, k8);
    cout << "输出: ";
    printArray(result8);
    cout << endl;
    cout << "期望: [4,-2,1,-3,5]" << endl << endl;
    
    // 测试案例9: 大窗口
    cout << "测试案例9 (大窗口):" << endl;
    vector<int> nums9 = {9, 10, 9, -7, -4, -8, 2, -6};
    int k9 = 5;
    cout << "输入: nums = ";
    printArray(nums9);
    cout << ", k = " << k9 << endl;
    vector<int> result9 = solution.maxSlidingWindow(nums9, k9);
    cout << "输出: ";
    printArray(result9);
    cout << endl;
    cout << "期望: [10,10,9,2]" << endl << endl;
    
    // 测试案例10: 空数组
    cout << "测试案例10 (空数组):" << endl;
    vector<int> nums10 = {};
    int k10 = 3;
    cout << "输入: nums = ";
    printArray(nums10);
    cout << ", k = " << k10 << endl;
    vector<int> result10 = solution.maxSlidingWindow(nums10, k10);
    cout << "输出: ";
    printArray(result10);
    cout << endl;
    cout << "期望: []" << endl << endl;
    
    return 0;
}